package cn.genmer.test.security.algorithm.sort;

import java.util.Arrays;

/**
 * @program: java8stream
 * @description: 将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。
 *
 * 通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 … 直到全部小的数组合并起来。
 * @时间复杂度： O(nlogn)
 * @空间复杂度： O(n)
 * @author: Genmer
 * @create: 2021-07-13 23:46
 **/
public class MergeSort {
    public static void main(String[] args) {
        int[] array = {1,8,7,4,3,6,9};
        System.out.println(String.format("排序前： %s", Arrays.toString(array)));
        sort1(array, 0, array.length-1);
        System.out.println(String.format("排序后： %s", Arrays.toString(array)));

    }

    /**
     * 老的sort
     * @param array
     * @return
     */
    private static int[] sort0(int[] array) {
        int[] arr = Arrays.copyOf(array, array.length);

        if (arr.length <2){
            return arr;
        }
        // 获取分割中点
        int middle = (int)Math.floor(arr.length/2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge0(sort0(left),sort0(right));
    }
    /**
     * 2022.11.23
     */
    public static void sort1(int[] arr, int left, int right) {
        if (left >= right) return;
        if (arr.length <2) return;
        // 获取分割中点
        int middle = left + (right-left)/2;

        sort1(arr, left,  middle);
        sort1(arr, middle+1, right);

        merge1(arr, left,middle+1, right);
    }

    /**
     * 老早写的
     * @param left
     * @param right
     * @return
     */
    private static int[] merge0(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;

        while (left.length > 0 && right.length > 0){
            if (left[0] < right[0]){
                result[i++] = left[0];
                left = Arrays.copyOfRange(left,1,left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right,1,right.length);
            }
        }

        while (left.length > 0){
            result[i++] = left[0];
            left = Arrays.copyOfRange(left,1,left.length);
        }

        while (right.length > 0){
            result[i++] = right[0];
            right = Arrays.copyOfRange(right,1,right.length);
        }
        return result;
    }

    /**
     * 2022.11.21 存在问题, 新的merge和旧的sort无法兼容
     * @return
     */
    private static int[] merge(int[] arr) {

        int size = arr.length;
        int mid = size/2;
        int[] temp = new int[arr.length];

        int i = 0;
        int j = mid+1;
        int tempIndex = 0;

        while (i <= mid && j < size){
            temp[tempIndex++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }

        while (i <= mid) temp[tempIndex++] = arr[i++];
        while (j < size) temp[tempIndex++] = arr[j++];

//        SelectSort.printArray(temp);
        return temp;
    }

    /**
     * 2022.11.23
     * @return
     */
    private static void merge1(int[] arr, int leftPtr, int rightPtr, int rightBound) {
        if (leftPtr >= rightPtr) return;
        int mid = rightPtr-1;
        int[] temp = new int[rightBound - leftPtr +1];

        int i = leftPtr;
        int j = rightPtr;
        int tempIndex = 0;

        while (i <= mid && j <= rightBound){
            temp[tempIndex++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }

        while (i <= mid) temp[tempIndex++] = arr[i++];
        while (j <= rightBound) temp[tempIndex++] = arr[j++];

        for (int k = 0; k < temp.length; k++) {
            arr[leftPtr+k] = temp[k];
        }
    }


    /**
     * 记忆重写
     * 2022.11.23 当天
     * 2022.11.25
     * @return
     */
    public static void sortTEST(int[] arr, int left, int right) {
        if (left >= right) return;
        if (arr.length < 2) return;

        int mid = left + (right-left)/2;
        sortTEST(arr, left, mid);
        sortTEST(arr, mid+1, right);

        mergeTEST(arr, left, mid+1, right);
    }
    /**
     * 记忆重写
     * 2022.11.23 不通过 1. 中位数计算写错 /2写成+1
     *                   2. merge 中位数写错 rightPtr-1 写成 l + (r -l)+1
     * 2022.11.24 半通过 1. merge的复制方法  arr[leftPtr +l] = temp[l] 写成  arr[l] = temp[leftPtr +l]
     * 2022.11.25 通过
     * 2022.11.29 不通过 while写法混了，记成了快排的嵌套while
     * 2022.11.30 半通过 最后复制 left和leftPtr写反了
     * @return
     */
    private static void mergeTEST(int[] arr, int leftPtr, int rightPtr, int rightBound) {
        if (leftPtr >= rightPtr) return;

        int mid = rightPtr-1;
        int left = leftPtr;
        int right = rightPtr;
        int tempIndex = 0;
        int[] temp = new int[rightBound - leftPtr+1];

        while (left <= mid && right <= rightBound) temp[tempIndex++] = arr[left] <= arr[right] ? arr[left++]: arr[right++];

        while (left <= mid) temp[tempIndex++] = arr[left++];
        while (right <= rightBound) temp[tempIndex++] = arr[right++];

        for (int i = 0; i < temp.length; i++) {
            arr[leftPtr + i] = temp[i];
        }

    }


}
